//https://leetcode.cn/problems/first-bad-version/submissions/
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

int firstBadVersion(int n) {
    long begin = 1;
    long end = n;

    while (begin <= end)
    {
        long mid = (begin + end) / 2;
        if (isBadVersion(mid))
        {
            end = mid - 1;
        }
        if (!isBadVersion(mid))
        {
            begin = mid + 1;
        }
    }
    return begin;
}